package leetcode_161_180;

import java.util.Arrays;

public class maximumGap_164 {
    /**
     * @param nums 无序的数组 nums
     * @return 返回 数组在排序之后，相邻元素之间最大的差值
     */
    public int maximumGap(int[] nums) {
        /**
         * 「线性时间」内运行并使用「线性额外空间」
         * 没有思路，因为我所会的排序都超过了这一时间复杂度
         * 但是又完全想不出来，不进行排序的解题思路
         * 学习了桶排序，但是桶排序极端情况下才能达到O(n)
         * 对于这一题并没有要求整个数组完全有序，达到宏观上的有序即可
         * 利用相邻箱子 min 和 max 的差值来解决问题
         * 同时需要保证每个箱子里边的数字一定不会产生最大 gap
         * 每个桶只存储了数组的一部分元素并且桶与桶之间的元素没有重复，可以想象成我们把数组分成了n段，这里只对每段求最小值，所以总时间还是O(n)
         */
        if (nums.length <= 1) {
            return 0;
        }
        int n = nums.length;
        int min = nums[0];
        int max = nums[0];
        //找出最大值、最小值
        for (int i = 1; i < n; i++) {
            min = Math.min(nums[i], min);
            max = Math.max(nums[i], max);
        }
        if(max - min == 0) {
            return 0;
        }

        //gap是相邻两个箱子的最小元素和最大元素的差值，而第一个箱子的最小元素前面已经没有相邻元素，
        //同理，最后一个箱子的最大元素后面也没有相邻元素，所以箱子中可以不放这两个元素，只对剩余的n - 2个元素分配箱子即可。

        //算出每个箱子的范围
        //保证每个箱子里边的数字一定不会产生最大 gap，并且尽量大的 interval
        //至少有一个空箱子，就可以断言，箱子内部一定不会产生最大 gap   -》gap 一定会大于 interval
        //有 n - 2 个数字，如果箱子数多于 n - 2 ，那么一定会出现空箱子。
        int interval = (int) Math.ceil((double)(max - min) / (n - 1));  //向上取整

        //每个箱子里数字的最小值和最大值
        int[] bucketMin = new int[n - 1];
        int[] bucketMax = new int[n - 1];

        //最小值初始为 Integer.MAX_VALUE
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        //最小值初始化为 -1，因为题目告诉我们所有数字是非负数
        Arrays.fill(bucketMax, -1);

        //考虑每个数字
        for (int i = 0; i < nums.length; i++) {
            //当前数字所在箱子编号
            int index = (nums[i] - min) / interval;
            //最大数和最小数不需要考虑
            if(nums[i] == min || nums[i] == max) {
                continue;
            }
            //更新当前数字所在箱子的最小值和最大值
            bucketMin[index] = Math.min(nums[i], bucketMin[index]);
            bucketMax[index] = Math.max(nums[i], bucketMax[index]);
        }

        int maxGap = 0;
        //min 看做第 -1 个箱子的最大值
        int previousMax = min;
        //从第 0 个箱子开始计算
        for (int i = 0; i < n - 1; i++) {
            //最大值是 -1 说明箱子中没有数字，直接跳过
            if (bucketMax[i] == -1) {
                continue;
            }

            //当前箱子的最小值减去前一个箱子的最大值
            maxGap = Math.max(bucketMin[i] - previousMax, maxGap);
            previousMax = bucketMax[i];
        }
        //最大值可能处于边界，不在箱子中，需要单独考虑
        maxGap = Math.max(max - previousMax, maxGap);
        return maxGap;

    }
}
